package cn.njupt.countSort;
//对CountingSort的优化，减少了内存的消耗并且写成了稳定的排序

import cn.njupt.cmpSort.Sort;
public class CountingSort2 extends Sort<Integer> {
//
    @Override
    public void sort() {
        //求最大值和最小值
        int max=array[0];
        int min=array[0];
        for (int i = 1; i < array.length; i++) {
            max=Math.max(max,array[i]);
            min=Math.min(min,array[i]);
        }

        //存放数组中元素出现的次数，数组的长度就是最大值减去最小值+1
        int[] counts=new int[max-min+1];
        //计算元素个数存放到help数组中
        for (int i = 0; i < array.length; i++) {
            counts[array[i]-min]++;
        }

        //累加次数，这边是最重要的，让计数排序变得稳定
        for (int i = 1; i <counts.length; i++) {
            counts[i]+=counts[i-1];
        }

        int[] target=new int[array.length];
        for (int i = array.length-1; i >=0; i--) {
            target[--counts[array[i]-min]]=array[i];
        }
        for (int i = 0; i < target.length; i++) {
            array[i]=target[i];
        }

    }
}
